package 力扣_树算法.遍历;

import java.util.*;

/**429.N叉树的层序遍历
 * @author zx
 * @create 2022-04-13 10:15
 */
public class N叉树的层序遍历_429 {
    /**
     * @return 递归
     */
    public List<List<Integer>> levelOrder2(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        helper(root,0,res);
        return res;
    }
    private void helper(Node root,int level,List<List<Integer>> res){
        if(root == null){
            return;
        }
        if(res.size() == level){
            res.add(new ArrayList<Integer>());
        }
        res.get(level).add(root.val);
        for(Node nodeChildren : root.children){
            helper(nodeChildren,level + 1,res);
        }
    }


    /**
     * @return 层序遍历
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for(int i = 0;i < size;i++){
                Node node = queue.poll();
                level.add(node.val);
                for(Node nodeChildren : node.children){
                    queue.offer(nodeChildren);
                }
            }
            res.add(level);
        }
        return res;
    }
}

